import java.util.Arrays;

//示例 1：
//回文的意思是正着念和倒着念一样，如：上海自来水来自海上
//        输入：s = "babad"
//        输出："bab"
//        解释："aba" 同样是符合题意的答案。
//        示例 2：
//        输入：s = "cbbd"
//        输出："bb"
//        示例 3：
//        输入：s = "a"
//        输出："a"
//        示例 4：
//        输入：s = "ac"
//        输出："a"
//        提示：
//        1 <= s.length <= 1000
//        s 仅由数字和英文字母（大写和/或小写）组成
//        来源：力扣（LeetCode）
//        链接：https://leetcode-cn.com/problems/longest-palindromic-substring
//        著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
public class Solution5 {
//    //错误
//    public static String longestPalindrome(String s) {
//        int[] ints = new int[128];
//        Arrays.fill(ints, -1);
//        String result =  s.substring(0,1);
//        int maxLength = 0;
//        for (int i = 0;i<s.length();i++){
//            int a = s.charAt(i);
//            if (ints[a]==-1){
//                ints[a]=i;
//            }else {
//                int length = i-ints[a]+1;
//                if (length>maxLength){
//                    maxLength = length;
//                    result = s.substring(ints[a],i+1);
//                }
//            }
//        }
//        return result;
//    }
public static String longestPalindrome(String s) {
    String result = "";
    for (int i = 0 ;i<s.length();i++){
        String res1 = getLongest(s,i,i);
        String res2 =  getLongest(s,i,i+1);
        result = res1.length()>result.length()?res1:result;
        result = res2.length()>result.length()?res2:result;
    }
    return result;
}
public static String getLongest(String s,int left,int right){
    while (left>=0&&right<s.length()){
        if (s.charAt(left)==s.charAt(right)){
            left--;
            right++;
        }else {
            break;
        }
    }
    //注意這裏要返回的是上一個,這個是剛好不符合條件 left要+1 right要-1  right+1是substr要多取一位
    return s.substring(left+1,right+1-1);
}

    public static void main(String[] args) {
        System.out.println(longestPalindrome("babadb"));
        System.out.println(longestPalindrome("cbbd"));
        System.out.println(longestPalindrome("a"));
        System.out.println(longestPalindrome("ac"));

    }
}

//拜读大佬们的题解，然后总结，有错误有疑惑的地方欢迎大家指正！
//
//       1. 理解题意
//        题目给定一个字符串
//        需要我们找到这个字符串中的最长回文串
//        回文串：正着读和反着读都一样的字符串
//        2.整体思路
//        我根据回文串的一个核心思想来解题：从中心点往两边扩散，来寻找回文串，这种方向相当于穷举每一个点为中心点
//        如果回文串是奇数时，比如 "bab" ，它的中心点就只有一个 "a"，所以从 "a" 开始向两边扩散
//        如果回文串是偶数时，比如 "baab"，它的中心点有两个 "aa"，所以从 "aa" 开始向两边扩散
//        编写一个辅助函数来寻找回文串，当中心点确定了之后调用辅助函数，直接返回找到的回文串
//        将每次找到的回文串与之前的做对比，谁长就留谁
//        3.代码大意：请看注释
//class Solution {
//    // 主函数
//    public String longestPalindrome(String s) {
//        // 记录最长回文串
//        String res = "";
//
//        // 穷举以所有点（奇数一个点，偶数两个点）为中心的回文串
//        for (int i = 0; i < s.length(); i++) {
//            // 当回文串是奇数时，由一个中心点向两边扩散
//            String s1 = palindrome(s, i, i);
//            // 当回文串是偶数时，由中间的两个中心点向两边扩散
//            String s2 = palindrome(s, i, i + 1);
//
//            // 三元运算符：判断为真时取冒号前面的值，为假时取冒号后面的值
//            res = res.length() > s1.length() ? res : s1;
//            res = res.length() > s2.length() ? res : s2;
//        }
//
//        return res;
//    }
//
//    // 辅助函数：寻找回文串
//    private String palindrome(String s, int left, int right) {
//        // 在区间 [0, s.length() - 1] 中寻找回文串，防止下标越界
//        while (left >=0 && right < s.length()) {
//            // 是回文串时，继续向两边扩散
//            if (s.charAt(left) == s.charAt(right)) {
//                left--;
//                right++;
//            } else {
//                break;
//            }
//        }
//
//        // 循环结束时的条件是 s.charAt(left) != s.charAt(right), 所以正确的区间为 [left + 1, right), 方法 substring(start, end) 区间是 [start, end), 不包含 end
//        return s.substring(left + 1, right);
//    }
//}